![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
A Feistel network is a general method of transforming any function (usually called the F function) into a permutation. It was invented by Horst Feistel [FNS75] in his design of Lucifer [Fei73], and popularized by DES [NBS77].
All commonly used symmetric block ciphers are product ciphers; they are strong ciphers constructed by many iterations of a round function, which is itself a kind of weak cipher. In a Feistel cipher, the round function consists of taking one part of the data being encrypted, feeding it into some key dependent function F, and then XORing (or otherwise combining) the result into another part of the block. If the part of the data used as input to the F function and the part of the data combined with output from the F function are each half of the block, then the cipher is a balanced Feistel network [SK96].
This is the basis of most block ciphers published since then, including FEAL [SM88], GOST [GOST89], Khufu and Khafre [Mer91], LOKI [BPS90, BKPS93], CAST-128 [Ada97a], Blowfish [Sch94], and RC5 [Riv95].
Two rounds of a Feistel network are collectively called a cycle [SK96]. In one cycle, every bit of the text block has been modified once.1 Twofish is a 16-round Feistel network with a bijective F function, which corresponds to eight cycles.
1 The notion of a cycle allows balanced Feistel networks to be compared with unbalanced Feistel networks [SK96, ZMI90] such as MacGuffin [BS95] (cryptanalyzed in [RP95a]) and Bear/Lion [AB96a], and with SP-networks (also called uniform transformation structures [Fei73]) such as SAFER and Shark [RDP+96] (see also [YTH96]). Thus, 8-cycle (8-round) SAFER is comparable to 8-cycle (16-round) DES and 8-cycle (32-round) Skipjack [NSA98].
Whitening, the technique of XORing key material before the first round and after the last round, was used by Ralph Merkle in Khufu/Khafre, and independently invented by Ron Rivest for DES-X [KR96a].
In [KR96a], it was shown that whitening substantially increases the difficulty of keysearch attacks against the remainder of the cipher. In our attacks on reduced-round Twofish variants, we discovered that whitening substantially increased the difficulty of attacking the cipher by hiding from an attacker the specific inputs to the first and last rounds F functions.
Twofish XORs 128 bits of subkey before the first Feistel round, and another 128 bits after the last Feistel round. These subkeys are calculated in the same manner as the round subkeys, but are not used anywhere else in the cipher.
An S-box is a table-driven non-linear substitution operation used in most block ciphers. S-boxes vary in both input size and output size, and can be created either randomly or algorithmically. S-boxes were first used in Lucifer, then DES, and afterwards in most encryption algorithms.
Twofish uses four different, bijective, key-dependent, 8-by-8-bit S-boxes. Each S-box is constructed using two fixed 8-by-8-bit permutations and several bytes of key material. These S-boxes can either be precomputed for a specific key, or computed on the fly for every required value. This provides a lot of flexibility and tradeoffs both in hardware and software.
A maximum distance separable (MDS) code over a field is a linear mapping from a field elements to b field elements, producing a composite vector of a + b elements, with the property that the minimum number of non-zero elements in any non-zero vector is at least b + 1 [MS77].2 Put another way, the distance (i.e., the number of elements that differ) between any two distinct vectors produced by the MDS mapping is at least b + 1. It can easily be shown that no mapping can have a larger minimum distance between two distinct vectors, hence the term maximum distance separable. MDS mappings can be represented by an MDS matrix consisting of a × b elements. Reed-Solomon (RS) error-correcting codes are known to be MDS. A necessary and sufficient condition for an a × b matrix to be MDS is that all possible square submatrices, obtained by discarding rows or columns, are non-singular.
2 We describe only the normal form of a linear MDS code. Any MDS code can be converted to an equivalent code in normal form.
Serge Vaudenay first proposed MDS matrices as a cipher design element [Vau95]. Shark [RDP+96] and Square [DKR97] use MDS matrices (see also [YMT97]), although we first saw the construction used in the unpublished cipher Manta [Fer96].3
3 Manta is a block cipher with a large block size and an emphasis on long-term security rather than speed. It uses an SP-like network with DES as the S-boxes and MDS matrices for the permutations.
MDS matrices are useful building blocks for ciphers because they guarantee a certain degree of diffusion. If one of the input elements is changed, all the output elements must change. If two input elements are changed, all but one of the output elements must change, etc. Twofish uses a single 4-by-4 MDS matrix over GF(28). This is one of the two main diffusion elements of Twofish. (There is also an RS-code with the MDS property used in the key schedule; this doesnt add diffusion to the cipher, but does add diffusion to the key schedule.)
A pseudo-Hadamard transform (PHT) is a simple mixing operation that is very efficient in software. Given two inputs, a and b, the 32-bit PHT is defined as:
a´ = a + b mod 232
b´ = a + 2b mod 232
SAFER [Mas94] uses 8-bit PHTs extensively for diffusion.
Twofish uses a 32-bit PHT to mix the outputs from its two parallel 32-bit g functions. This PHT can be executed in two opcodes on most modern microprocessors, including the Pentium family. This is the second main diffusion element in Twofish.
The key schedule is the means by which the key bits are turned into round keys that the cipher can use. The requirements call for a variable-length key. The easiest way of using this is to have a key schedule that expands a variable-length key to a fixed set of expanded key values.
Twofish needs a lot of key material, and has a complicated key schedule. To facilitate analysis, the key schedule uses the same primitives as the round function. Except for two additional rotations, each pair of expanded key words is constructed by applying the Twofish round function (with key-dependent S-boxes) to a fixed input.
Previous | Table of Contents | Next |